1. Field of the Invention
(U) The present invention relates generally to a method or apparatus for creating a data structure for use in either a ranging signal or the synchronization preamble of a digital communications signal. More specifically, the invention relates to an embedded data structure that hides the ranging signal or synchronization preamble from an unauthorized user.
2. Description of the Related Art
(U) The Global Positioning System (GPS) system uses ranging signals transmitted by satellites orbiting the earth (launched and operated by the U.S. military) and received by special radio receivers (operated by U.S. military or civilians). This system facilitates accurate determination of the position (map coordinates and altitude) of people, vehicles, and stationary sites anywhere on the earth (where the sky is visible). A Russian system (GLONASS) and a European system in development have generally similar goals and operation. These systems can also be used to determine the position of other satellites.
(U) In general, the transmitted ranging signal has a time-varying structure that is related in a pre-determined way to the transmitter's clock. The receiver generally generates (internally) a duplicate signal (called the reference signal) related in the same manner to its own clock. By comparing the received signal to the reference signal, the receiver can measure the time of arrival (according to its own clock) of any selected portion of the received signal. This comparison is basically done by trying various timings of the reference signal (some earlier, some later) until a reference timing is found that is nearly identical to the timing of the received signal. To reliably detect such a time alignment when the received signal is weak and noisy, the correlation of the received and reference signals is computed. This correlation effectively measures the similarity of the two (tentatively time-aligned) signals over some interval of time. The detection of the received signal and measurement of its time of arrival is more reliable as the correlation interval is made longer.
(U) The measured time of arrival depends on the discrepancy (disagreement) between the transmitter's and the receiver's clocks, and the distance between the transmitter (satellite) and the receiver (user) at the time of the measurement. The measurement is generally interpreted as a pseudorange, that is, the distance plus the clock discrepancy times the speed of light (speed of the radio signal).
(U) Each satellite transmits a different (unique) ranging signal. A receiver can measure the pseudorange to any satellite that is in view by using a duplicate of that satellite's signal as its reference signal. Some receivers (generally those that are stationary) measure the pseudoranges one satellite at a time. Other receivers (generally those that are moving rapidly) measure the pseudoranges concurrently, using more circuitry. In general, the position of the transmitter (satellite) at the time of each pseudorange measurement is known (from orbital data), and the position of the receiver (user) at the time of the pseudorange measurements is unknown.
(U) The mathematics for computing the unknowns (receiver position and clock discrepancy) from the known data and measurements is well documented. Generally four pseudoranges need to be measured, but more pseudorange measurements and/or selecting a favorable set of satellites can improve the accuracy of the results. (Usually six or seven satellites are visible at once.)
(U) Typically, a receiver will initially have only approximate orbital data for the satellites, and its clock may be accurate only to within ten seconds of correct time. This will hinder the ability of the receiver to initially align the timing of its reference signal to the received signal of any of the currently visible satellites. The process of finding the correct timing and thus detecting the received signal is called signal acquisition. After the timing of the first satellite is acquired, the receiver is able to receive a data message (providing more accurate and up-to-date orbital data) that is superimposed on the ranging signal, and can partly correct its clock timing (because the satellite clock accuracy is much better). This makes acquisition of the signals from the remaining satellites easier.
(U) Suppose the ranging signal pattern is a random (but known) sequence of chips (the smallest detail of the signal pattern) at the rate of 10,000,000 chips per second. The received and reference signals must be aligned to within half a chip for the correlation process to detect the received signal, and the possible alignments cover a range of twenty seconds. Thus, there are 400,000,000 possible time alignments to be tried; that is, that many correlations to be computed. If, for example, a correlation interval of one-tenth of a second is needed, and the receiver is equipped with 2,000 correlators, the receiver will be able to try 20,000 alignments per second, taking 20,000 seconds (400,000,000 divided by 20,000), that is, 5.55 hours to try all of the possible alignments. This is clearly not practical. (The satellite may not even by visible that long.) A slower chip rate would allow faster acquisition, but would provide less accurate position measurements.
(U) The design is limited by the fact that the signal is a broadcast signal; that is, there are many receivers for each transmitted signal. Since many receivers must operate simultaneously and independently, including independent starting and stopping of the operation of the receivers, each transmitted signal must continuously provide all of the needed information.
(U) GPS solves this problem by providing two ranging signals for each satellite in a constellation of 24 satellites. First, a Coarse Acquisition (C/A) signal is provided at 1,023,000 chips per second with a known pattern that repeats 1,000 times per second. Secondly, a Precision (P) signal is provided at 10,230,000 chips per second with a known pattern that repeats once a week. The C/A signal can be acquired quickly, providing modest navigational accuracy. The information thus gained allows the P signal to be acquired next, providing more navigational accuracy. Furthermore, a “Navigation” message providing up-to-date orbital data for all satellites is superimposed on one or both ranging signals from each satellite. This data not only helps the receiver to compute its location, but also helps to process the received signals more effectively.
(U) Civilians and the military can both use GPS for peaceful purposes, which are generally navigation (location of moving vehicles) and surveying (location of stationary sites). For such use, protection against improper use, and interference with the proper use, of the system is protected by law and law enforcement, and limited by the cost of such action to a criminal or gang. However, in time of war, international disagreement and military might supercede law and law enforcement, and the resources of a nation generally outweigh those of a criminal or gang. In this context, GPS can potentially be used to guide missiles and military vehicles, and to locate military targets. Thus it is (and has always been) important to the U.S. military to be able to control the signals from the GPS satellites to: 1) restrict the use of these signals by enemy forces (e.g., aiming weapons at us), 2) provide the highest accuracy for the U.S. military (e.g., aiming weapons at them), 3) resist the interference of goal 2 (above) by enemy forces (e.g., jamming and spoofing), and 4) provide modest accuracy for peacetime and civilian use. An enemy jamming signal would try to prevent us from receiving and using the GPS signals. An enemy spoofing signal would try to confuse us by causing us to unknowingly compute wrong data.
(U) GPS has provided signal modes to address the above goals. One mode allows a “Y” signal to be substituted for the P signal. The Y signal is a non-repeating secret pattern known only to U.S. military receivers. This was designed to make a ranging signal useful to U.S. military receivers but not to any other receivers. Other modes degrade the accuracy of the C/A and P(Y) ranging signals, but secret data is made available to U.S. military receivers allowing them to compensate for these signal degradations.
(U) Historically, GPS was made primarily for U.S. military use, but secondarily, it was made available to peacetime civilian use. The above modes were available for use in the event of war. But several developments eventually provided motivation for a change of strategy. The global threat shifted from a ‘cold war’ standoff to more localized conflicts such as the Gulf War. This motivates more local rather than global control of GPS as a military resource. Worldwide civilian use grew beyond all expectations, creating a competitive global market for GPS technology. This developed an economic threat to U.S. business. GLONASS performance was significantly less than GPS, with questionable support. The European Union (EU) became seriously interested in developing its own alternative ‘GPS’. This threatens U.S. military interests and U.S. business interests. Accuracy was soon recognized to be better than expected; and many new techniques have since been developed to further increase the accuracy, including for civilian use. This has been encouraging to the civilians, especially the airline industry (which now recognizes the feasibility of using GPS for aircraft landing guidance), but worrisome to the military.
(S) Additionally (6), one of the manufacturers of civilian GPS receivers has discovered and exploited a flaw in the construction of the Y signal, allowing civilian use of the Y signal without access or use of any secret data.
(U) These developments put the U.S. civilian and military sectors at odds in a political debate. If the military continue to protect their interests only by globally degrading the civilian quality of GPS, then eventually, the EU would satisfy the civilian needs with their system. This would be bad news to both U.S. business and the U.S. military. The U.S. economy would lose business to other countries, and U.S. military control would be diluted.
(U) This situation can be resolved by the following strategy. Give the civilian sector global access to the C/A and P ranging signals with a guaranteed level of accuracy (no degradation of quality). However, in war zones, the U.S. military can locally suppress the C/A and/or P signals. For example, the C/A signal can be jammed, and this would suppress acquisition of the P signal. For use in war by the U.S. military, provide a new Military Access (MA) ranging signal. This signal needs to have the following attributes: It should be usable only by the U.S. military. (Secret data is needed to understand the signal.) It should be resistant to jamming and to spoofing.
(U) However, a signal pattern with sufficient detail to provide high precision inherently cannot be acquired quickly (as explained above). This is especially problematic for military applications because of the presence of jamming and the needs of high precision and fast acquisition. This situation suggests the use of separate military ranging signals for acquisition and tracking, analogous to the C/A and P ranging signals available for civilian use.
(U) One design method for the new Military Access (MA) signal is to use an unstructured (perfectly random) sequence of bits (also called chips) at a high rate (typically 10 MHz), using a cryptographic algorithm to generate the sequence deterministically and synchronized to clock time. That is, any receiver that has the cryptographic algorithm, the secret key used to control the cryptographic algorithm, and correct clock timing, can generate the same random sequence generated by the transmitter. (As explained earlier, by generating a reference signal, a receiver can search for and detect a similar received signal.) If the receiver's clock timing is in error, which is usually the case, this error will simply add to the uncertainty of the transit time of the signal from the transmitter to the receiver. This type of signal has the attributes of being usable by the U.S. Military, and of being resistant to jamming and spoofing. It also works very well for the tracking mode of the receiver, but it works poorly for acquisition.
(C) It has been proposed that a structured signal should be embedded within the unstructured signal described above. (Embedded means that selected bits of the unstructured signal are replaced with bits that comprise the structured signal. A few authors call the embedding “puncturing”, but in the general literature of signal coding, puncturing refers to removal of code elements, not replacement.) The basic idea is that the embedded structured signal would be designed to aid acquisition while not interfering with tracking. An embedded signal avoids much of the costs of a separate acquisition signal. It also needs to have the attributes of being usable by the U.S. Military, and of being resistant to jamming and spoofing. As implemented by the present invention, the embedded signal would also be ‘invisible’ (completely undetectable) by receivers that lack the secret data used in its construction.
(C) It is generally recognized that in order to obtain the required attributes, the embedded signal will need to have randomized parameters. That is, the code construction will use random values generated by the cryptographic algorithm, which is controlled by clock time and by secret data. Thus, only receivers that have the cryptographic algorithm and the secret data (U.S. military receivers) will be able to determine the values of these parameters for any given time of the day. Because the values are random, other observers will not be able to learn from previous values how to guess future values.
(S) A number of embedded signal structures have been proposed. One type called GRASP or GRASP-lite, embeds multiple copies of a block of random bits in random positions (at random times). Another type called CCAS1, constructs larger blocks from smaller blocks by randomly varying the polarities of the copies of the smaller blocks. The larger blocks are repeated, and the time positions of the small and large blocks are randomly varied. (Random bits, random times, and random polarities are examples of randomized parameters.)
(U) In addition to the GPS signal structures discussed above, there are other signaling and messaging applications where the present invention can be used. It is common in digital communications to prefix to each message a synchronization pattern. The purpose of this pattern is to help the receiver to lock onto the bit rate and phase, and to determine reliably the precise start of the message content. That is, such a pattern is also an “acquisition aid”. The requirement to detect the precise time of arrival reliably is similar to the requirement for ranging signals. In a military environment, these synchronization preambles also need to be resistant to jamming and to spoofing.
(S) The proposed signal structures briefly described above fail to adequately provide the attributes of being usable by the U.S. Military, and of being resistant to jamming and spoofing. Mainly, resistance to spoofing and jamming is inadequate. An enemy receiver designed to search for repeated data can detect the repetition of data blocks. When a first repeat is detected, then the data that is repeated is also detected, and this can be used to detect subsequent repetitions of the same data. A jammer that is guided by such a receiver can expend its available power on jamming most of the repeated blocks, rather than jamming all of the signal. That is, when the onset of a repeat block is detected, the jammer is switched on to jam the remainder of the block. Jamming the part of the signal most needed for acquisition gives the enemy the advantage of doing more damage for a given amount of power, or, requiring less power to inflict sufficient damage, or, extending the effective range of the jammer. Enemy detection of repeat blocks can also be used for spoofing, by mimicking critical portions of the signal. The enemy's cost for detection of repeat blocks is estimated to be of the same order of magnitude as the detection cost of an authorized (U.S. military) receiver.
(S) This weakness with regard to enemy detection can be minimized by reducing the number of repetitions or by reducing the size of the repeated blocks. But these reductions also weaken the ability to aid acquisition by authorized receivers. This need to trade off the ease of enemy detection vs. the ease of authorized detection limits the choice of signal parameters.
(S) There is a need for flexibility in the design of military receivers, because some military applications require faster acquisition than others, some need more jamming resistance (operate closer to the enemy), some move faster and have greater velocity uncertainty, etc. Since the receivers designed for these applications must all use the same signals from the same constellation of satellites, the design of the signals transmitted by the satellites must suffice for the diverse needs of all of the receivers. This need for flexibility is restrained by the above limitation of signal parameter choices.
(S) Additionally, for one of the proposed signals, the definition of the signal timing allows enemy receivers to obtain useful ranging information from the signal without access to secret data. This signal thus fails to provide the attribute that the signal be usable by only the U.S. military.